/**
 * Copyright (C) 2008+ Spark Zheng
 *
 * @file	include/htable.h
 * @brief 
 *      Hashtable module, A basic datastruct module.
 *      Memory-free operations, generic frame of hash-table datastructs
 *      Thread-safe htable implementation
 *      -1. chaining htable
 *      -2. open-addressing htable
 *
 * @module      dlib
 * @see		dlib
 *
 * @history
 *	version 0.1.0, spark init htable module with chaining-htable 
 *	version 0.2.0, spark add open-addressing-htable
 *	version 0.3.0, spark add simple chaining-htable module
 */

#ifndef _DLIB_HTABLE_H
#define _DLIB_HTABLE_H

#ifdef __cplusplus
extern "C" {
#endif

#include "global.h"
#include "list.h"
#include "lock.h"
#include "mempool.h"

/**
 * ht_relval_fn, release the val when needed.
 */
typedef void (*ht_relval_fn)(void *val);

/**
 * ht_walker_fn, travel the htable nodes, and do something.
 */
typedef void (*ht_walker_fn)(const void *k, const void *v, void *arg);

/**
 * ht_compare_fn, key-compare function for set/get/del.
 * @return (one to two) 0 equal, -1 little, 1 great.
 */
typedef int (*ht_compare_fn)(const void *one, const void *two);

/**
 * 32bit ht_hash_fn, key-hash function.
 * @return uint32_t.
 * @param k: the key need be hashed
 * @param other: other parameter.
 */
typedef uint32_t (*ht_hash_fn)(const void *k, void *other);


/**
 * simple chaining-htable implementation
 * from YAEZ-server-framework by Magic Zhao
 */
typedef struct hnode_naive	hnode_naive_t;
typedef struct htable_naive	htable_naive_t;

struct hnode_naive {
	void		*hn_key;	/* key field */
	void		*hn_val;	/* value field */
	hnode_naive_t	*hn_next;	/* link list next pointer */
};

struct htable_naive {
	dlib_alloc_t	*ht_na;		/* memory allocator */
	ht_hash_fn	ht_hfunc;	/* hash function */
	void		*ht_harg;	/* hash function argument */
	ht_compare_fn	ht_cfunc;	/* equal function for search */
	int		ht_bucket_size;	/* bucket count in hash table */
	hnode_naive_t	*ht_buckets[0];	/* bucket array */
};

#define HTABLE_NAIVE_SIZE(size)	(sizeof(htable_naive_t) + ((size) << 2))

/**
 * ht_naive_init
 * @brief init a hash table
 * @return a new allocated htable_naive_t pointer, NULL if memory used out
 * @param na: memory allocator
 * @param span: capacity of hash table
 * @param h: hash function pointer
 * @param arg: hash function argument
 * @param c: equal function pointer
 */
extern htable_naive_t *ht_naive_init(dlib_alloc_t *na, int span,
		ht_hash_fn h, void *arg, ht_compare_fn c);

/**
 * ht_naive_get
 * @brief find a key in hash table, if found value field is returned
 * @return 0 found, -1 not found
 * @param ht hash table object
 * @param key key field to be found
 * @param val output result to value field
 */
extern int ht_naive_get(htable_naive_t *ht, void *key, long **val);

/**
 * ht_naive_insert
 * @brief insert a key value pair to hash table when item not exist
 * @return 0 success, -1 item exist, -2 failed
 * @param ht pointer to hash table object
 * @param key pointer to key field
 * @param val pointer to value field
 */
extern int ht_naive_insert(htable_naive_t *ht, void *key, void *val);

/**
 * ht_naive_set
 * @brief insert a key value pair to hash table no matter item exist
 * @return 0 success, -1 failed
 * @param ht pointer to hash table object
 * @param key pointer to key field
 * @param val pointer to value field
 */
extern int ht_naive_set(htable_naive_t *ht, void *key, void *val);

/**
 * ht_naive_del
 * @brief remove a key value pair from hash table
 * @return 0 success, -1 failed
 * @param ht pointer to hash table object
 * @param key pointer to key field
 */
extern int ht_naive_del(htable_naive_t *ht, void *key);


/**
 * thread-safe chaining-htable, suitable for N(elements) > M (buckets)
 * the key APIs:
 * 1. ht_set(insert)
 * 2. ht_get(lookup)
 * 3. ht_del(delete)
 * 4. ht_walker(travel)
 */
typedef struct hnode    hnode_t;
typedef struct htable   htable_t;

#ifdef _DEBUG
typedef struct htstatics htstatics_t;
	
struct htstatics {
	uint32_t	hs_gets;	/** get-op counts */
	uint32_t	hs_sets;	/** set-op counts */
	uint32_t	hs_dels;	/** del-op counts */
	uint32_t	*hs_buckets_num;
	
	dlib_lock_t     hs_lock;
};
#endif
	
struct hnode {
	void		*key;		/** node key */
	void		*val;		/** node value */
	hlist_node_t	hl;		/** hlist node member */
	
	dlib_lock_t	hn_lock;	/** hnode lock */
};

struct htable {
	uint32_t	ht_id;		/** htable id */
	uint32_t	ht_span;	/** buckets number of hash table, primer */
	uint32_t	ht_count;	/** entry count of hash table */

#ifdef _DLIB_HTABLE_USE_MARENA
	dlib_marena_t	*ht_p;		/** memory arena of hash table */
#endif
	
	uint16_t	ht_key_freed;	/** need free key by hand */
	ht_relval_fn	ht_rel_val;	/** release val function */

	dlib_lock_t	*b_locks;	/** list of buckets locks */
	hlist_head_t	*buckets;	/** list of buckets */

	uint32_t	iter_bucket;	/** iterator bucket for ht_walker */
	hnode_t		*iter_node;	/** iterator for ht_walker */

	ht_hash_fn	ht_hash;	/** hash function, allow to be NULL */
	void		*ht_hash_arg;	/** hash function argument */

	ht_compare_fn	ht_compare;	/** compare function, not to be NULL */
	
	dlib_lock_t     ht_lock;	/** htable lock */

#ifdef _DEBUG
	htstatics_t	*ht_statics;	/** htable statics */
#endif
};

/**
 * ht_init
 * @brief build up a hash table
 * @return NULL or new htable struct
 * @param span: htable span, usually a primer.
 * @param h: the hash function
 * @param arg: hash function args
 * @param c: the compare function, return -1(minor)/0(equal)/1(superior)
 * @param key_freed: need free key by hand
 * @param r: the release value function
 */
extern htable_t *ht_init(uint32_t span, ht_hash_fn h, void *arg,
			 ht_compare_fn c, uint16_t key_freed,
			 ht_relval_fn r);

/** 
 * ht_exit
 * @brief destroy a hash table
 * @param table: htable struct.
 */
extern void ht_exit(htable_t *table);

/** 
 * ht_set
 * @brief insert a K-V pair to htable, will overwrite the duplicate.
 * @return 0(success) / <0(error)
 * @param table: htable struct.
 * @param k: key of node
 * @param v: value of node
 */
extern int ht_set(htable_t *table, void *k, void *v);

/** 
 * ht_get
 * @brief fetch a K-V pair from htable.
 * @param return NULL(no such key) / value
 * @param table: htable struct.
 * @param k: key of node
 */
extern void *ht_get(htable_t *table, const void *k);

/** 
 * ht_del
 * @brief delete a K-V pair from htable.
 * @return 0(success) / <0(error)
 * @param table: htable struct.
 * @param k: key of node
 */
extern int ht_del(htable_t *table, const void *k);

/** 
 * ht_walker_from
 * @brief set the walker starting point of htable.
 * @return 0(success) / <0(error)
 * @param table: htable struct.
 * @param k: the start key, if k == NULL, begin with the first node.
 */
extern int ht_walker_from(htable_t *table, const void *k);

/** 
 * ht_walker
 * @brief walker over a htable, execute function for each node or from iter.
 * @return 0(success) / <0(error)
 * @param table: htable struct.
 * @param w: walker function
 * @param arg: walker argument(could be NULL)
 */
extern int ht_walker(htable_t *table, ht_walker_fn w, void *arg);

/** 
 * ht_dump
 * @brief dump out from htable.
 * @param table: htable struct.
 */
extern void ht_dump(htable_t *table);


/**
 * thread-safe open-addressing-htable, suitable for N (elements) < M (buckets)
 * use multi-hash-detecting method for colision.
 * if need less buckets, think about judy-array.
 * open-addressing-htable APIs:
 * 1. ht_open_set(insert)
 * 2. ht_open_get(lookup)
 * 3. ht_open_del(delete)
 * 4. ht_open_walker(travel)
 * 5. ht_open_expand
 * 6. ht_open_rehash
 */
typedef struct hnode_open       hnode_open_t;
typedef struct htable_open      htable_open_t;

#ifdef _DEBUG
typedef struct htstatics_open   htstatics_open_t;
	
struct htstatics_open {
	uint32_t	hs_gets;	/** get-op counts */
	uint32_t	hs_sets;	/** set-op counts */
	uint32_t	hs_dels;	/** del-op counts */
	uint32_t	hs_collisions;  /** collisions */
	
	dlib_lock_t     hs_lock;
};
#endif

struct hnode_open {
	void	    *key;
	void	    *val;
};

struct htable_open {
	uint32_t	ht_id;
	uint32_t	ht_span;
	uint32_t	ht_count;

#ifdef _DLIB_HTABLE_USE_MARENA
	dlib_marena_t	*ht_p;		/** memory arena of hash table */
#endif

	hnode_open_t    **buckets;    

	uint16_t	 ht_key_freed;
	ht_relval_fn    ht_rel_val;

	ht_hash_fn	ht_hash;	/** hash function, allow to be NULL */
	void		*ht_hash_arg;	/** hash function argument */

	ht_compare_fn	ht_compare;	/** compare function, not to be NULL */

	dlib_lock_t     ht_lock;

#ifdef _DEBUG
	htstatics_open_t *ht_statics;   /** htable statics */
#endif
};

/**
 * ht_open_init
 * @brief build up an open-addressing hash table
 * @return NULL or new htable struct
 * @param span: htable span, usually a primer.
 * @param h: the hash function
 * @param arg: hash function args
 * @param c: the compare function, return -1(minor)/0(equal)/1(superior)
 * @param key_freed: need free key by hand
 * @param r: the release value function
 */
extern htable_open_t *ht_open_init(uint32_t span, ht_hash_fn h, void *arg,
				   ht_compare_fn c, uint16_t key_freed,
				   ht_relval_fn r);

/** 
 * ht_open_exit
 * @brief destroy an open-addressing hash table
 * @param table: htable struct.
 */
extern void ht_open_exit(htable_open_t *table);

/** 
 * ht_open_set
 * @brief insert a K-V pair to htable, will overwrite the duplicate.
 * @return 0(success) / <0(error)
 * @param table: htable struct.
 * @param k: key of node
 * @param v: value of node
 */
extern int ht_open_set(htable_open_t *table, void *k, void *v);

/** 
 * ht_open_get
 * @brief fetch a K-V pair from htable.
 * @param return NULL(no such key) / value
 * @param table: htable struct.
 * @param k: key of node
 */
extern void *ht_open_get(htable_open_t *table, const void *k);

/** 
 * ht_open_del
 * @brief delete a K-V pair from htable.
 * @return 0(success) / <0(error)
 * @param table: htable struct.
 * @param k: key of node
 */
extern int ht_open_del(htable_open_t *table, const void *k);

/** 
 * ht_open_walker
 * @brief walker over a htable, execute function for each node or from iter.
 * @return 0(success) / <0(error)
 * @param table: htable struct.
 * @param w: walker function
 * @param arg: walker argument(could be NULL)
 */
extern int ht_open_walker(htable_open_t *table, ht_walker_fn w, void *arg);

/**
 * ht_open_expand
 * @brief expand the open-addressing htable with new size.
 * @return 0(success) / <0(error)
 * @param table: htable struct
 * @param span: new span of htable, need be a bigger primer
 */
extern int ht_open_expand(htable_open_t *table, uint32_t span);

/**
 * ht_open_rehash
 * @brief
 *      After expand or deletions, htable need to be rehashed
 *      the rehash operation would be time-consuming  
 * @return 0(success) / <0(error)
 * @param table: htable struct
 */
extern int ht_open_rehash(htable_open_t *table);

/** 
 * ht_open_dump
 * @brief dump out from htable.
 * @param table: htable struct.
 */
extern void ht_open_dump(htable_open_t *table);


#ifdef __cplusplus
}
#endif
#endif
